/*
https://leetcode.cn/problems/house-robber-ii/description/
213. 打家劫舍 II
medium, 彭珵 2024.9.3
*/

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0]; 

        int max1 = robLinear(vector<int>(nums.begin() + 1, nums.end()));
        
        int max2 = robLinear(vector<int>(nums.begin(), nums.end() - 1));

        return max(max1, max2); 
    }

    int robLinear(const vector<int>& nums) { 
        int n = nums.size();
        if (n == 0) return 0; 
        if (n == 1) return nums[0]; 

        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
};